#ifndef __RUNFINDER__H
#define __RUNFINDER__H
#include "Image.h"
#include <vector>

struct Run {
	S32 m_nStartPos;
	S32 m_nLength;
	S32 EndPos() const { return m_nStartPos + m_nLength - 1; }
	S32 AvgPos() const { return (m_nStartPos + EndPos()) / 2; }
};

template <class SOURCE>
class RunFinder {
public:
	RunFinder(SOURCE *pImage) : m_pImage(pImage) {}	
	S32 GetRunsForRow(S32 nRow, U8 nColor, std::vector<Run> *pListOfRuns) {
		Rect<S32> boundingRect;
		m_pImage->GetBoundingRect(&boundingRect);
		pListOfRuns->clear();
		if (nRow < boundingRect.Top() || nRow > boundingRect.Bottom()) {
			return 0;
		}
		
		S32 nCol = boundingRect.Left();
		S32 nColLimit = boundingRect.Right();
		Run run;
		run.m_nLength = 0;
		while(nCol <= nColLimit) {
			if (m_pImage->GetPix(nRow, nCol) == nColor) {
				if (run.m_nLength++ == 0) 
					run.m_nStartPos = nCol;
			} else {
				if (run.m_nLength) pListOfRuns->push_back(run);
				run.m_nLength = 0;
			}
			++nCol;
		}
		return pListOfRuns->size();
	}
	Run GetHorzRunForPoint(S32 nRow, S32 nCol, U8 nColor) {
		Run run;
		S32 nOrigCol = nCol;
		run.m_nStartPos = run.m_nLength = 0;
		while(m_pImage->GetPix(nRow, nCol--) == nColor)
			++run.m_nLength;
		run.m_nStartPos = nCol + 2;
		nCol = nOrigCol;
		while(m_pImage->GetPix(nRow, ++nCol) == nColor)
			++run.m_nLength;
		return run;
	}
	Run GetVertRunForPoint(S32 nRow, S32 nCol, U8 nColor) {
		Run run;
		S32 nOrigRow = nRow;
		run.m_nStartPos = run.m_nLength = 0;
		while(m_pImage->GetPix(nRow--, nCol) == nColor)
			++run.m_nLength;
		run.m_nStartPos = nRow + 2;
		nRow = nOrigRow;
		while(m_pImage->GetPix(++nRow, nCol) == nColor)
			++run.m_nLength;
		return run;
	}
	void GetAdjacentVertRuns(Run run, S32 nCol, U8 nColor, std::vector<Run> *pListOfRuns) {
		S32 nRow = run.m_nStartPos;
		S32 nRowLimit = run.m_nStartPos + run.m_nLength; 
		while(nRow < nRowLimit) {
			if (m_pImage->GetPix(nRow, nCol) == nColor) {
				Run r;
				pListOfRuns->push_back(r = GetVertRunForPoint(nRow, nCol, nColor));
				nRow = r.m_nStartPos + r.m_nLength;
			} 
			++nRow;
		}
	}
	
	/** @return if there is not common run, returns a run where m_nLength == 0 */
	Run GetCommonAdjacentVertRun(Run runTop, Run runBottom, S32 nCol, U8 nColor) {
		Run r1 = GetVertRunForPoint(runTop.EndPos(), nCol, nColor);
		Run r2 = GetVertRunForPoint(runBottom.m_nStartPos, nCol, nColor);
		if (r1.m_nStartPos == r2.m_nStartPos) return r1;
		r1.m_nLength = 0;
		return r1;
	}
private:
	SOURCE *m_pImage;
};
#endif
